Periodic schedules are seldom treated in the theory but abound in practice (air flight schedule, train schedule, manufacturing schedule, etc). This paper introduces a Petri Net based perspective to periodic schedules. These are classified, according to the time interpretation into single-server and multiple-server semantics and, according to transitions firing periodicity constraints, into strict and general periodic schedules. Using a net transformation rule, the computation of the general schedule class can be done through techniques for the strict subclass. Introducing truncation error terms ε for the floor functions, a necessary and sufficient condition for the feasibility of a strict periodic schedule is given in terms of a large size system of nonlinear inequalities containing ε terms. Moreover averaging this condition on subperiods allows to get a small size linear system of inequalities as necessary conditions for speeding up iterative computation processes. This paper aims to present qualitative analysis of periodic schedules for deterministically timed Petri net systems, as a precursor to quantitative analysis that requires large-scale computational experiments and hence will be dealt in later work.

Free choice nets are a class of Petri nets, which can represent the substantial features of systems by modeling both choice and concurrency. And in the modelling and design of a large number of concurrent systems, live and safe free choice nets (LSFC nets) have been explored their structural characteristics. On the other hand, state machine decomposable nets (SMD nets) are a class of Petri nets which can be decomposed by a set of strongly connected state machines (S-decomposition). State machine allocatable nets (SMA nets) are a well-behaved class of SMD nets. Of particular interest is the relation between free choice nets and SMA nets such that a free choice net has a live and safe marking if and only if the net is an SMA net. That is, the structure of an LSFC net is an SMA net. Recently, the structure of SMA net has been completely characterized by the authors based on an S-decomposition. In other words, a necessary and sufficient condition for a net to be an SMA net is obtained in terms of the net structure where synchronization between strongly connected state machine components (S-components) has been clarified. Unfortunately, it requires tremendous amount of time and spaces to decide a given net to be an SMA net by applying the condition directly. Moreover, there exist no efficient algorithm to decide the liveness and safeness of a given SMA net that lessens the usefulness of decomposition techniques. In this paper, we consider efficient polynomial order algorithms to decide whether a given net is a live and safe SHA net.

Marc Kellner proposed an example problem intending to compare modeling and describing techniques of software process. In this paper, we will describe our approach to understanding and describing the problem, from a process/product relation view, and synchronization/concurrent view. Also, we will show that a description of the problem is translated for execution and its correctness is validated.

This paper describes a programming system, K-NET for the development of control software for flexible manufacturing systems composed of robots, numerically-controlled machines, transfer machines and automatic storage/retrieval systems. K-NET is based on a high-level Petri net which makes it simple to express operational functions such as synchronization, interlock and concurrence in sequence control. Petri net in K-NET is colored one in which tokens have attributes, and timed one which can provide a notion of stochastic time. K-NET provides many kinds of boxes having specific functions, and gates specified the firing condition and the token flow control with IF-THEN rules. On the other hand, procedural language can be also used for information processing. K-NET can support all development stages including general design, detailed design, programming and testing. K-NET has an editor to input control specifications expressed with Petri net; a simulator to verify edited specifications; a generator to convert the net to C source programs for a computer or to ladder diagrams for a programmable controller; a reporter to print control specifications; and a monitor to display controller status in real-time. K-NET has been used in the development of control software for an automated guided vehicle system, and results show a 2/3rds cost-saving over development with conventional methods in which only procedural language is used.

An integrated platform INTEGRAL has been developed for developing large complex communication software systems. At the heart of INTEGRAL, a pair of graphical and textual specification languages, DISCOL (DIStributed Communication-Oriented Language), has been developed based on Petri nets. Around DISCOL, a wide variety of design and analysis tools have been integrated in coherent manner so that a seamless support from design to verification and testing are made available along with software life-cycle. The platform has been applied to the development of a PBX simulator named UICPBX. In the development, some real communication services have been fully specified with DISCOL. Such experiences have revealed the effectiveness of the proposed techniques.

The pursuit of higher availability has resulted in the development of fault tolerant systems for many industries. However, system characteristics that can be perceived by the customer have never been diagnosed quantitatively. This paper considers the application of stochastic Petri nets with general firing times to modeling of a fault tolerant system and the use of discrete-event simulation methods for stochastic Petri nets to study the behavior of the system. The stochastic Petri net model incorporates factors that compose the system as well as those that accompany it, including RAS characteristics of products, personnel arrangements, and system management. By modeling the behavioral aspect of each factor, it is possible to diagnose a fault tolerant system quantitatively on the basis of customer impact.

This paper describes MENDELS ZONE, a Petri-net-based concurrent programming environment, which is especially suitable for cooperating discrete event systems. MENDELS ZONE adopts MENDEL net, which is a type of high level (hierarchical colored) Petri net. One of the characteristics of the MENDEL nets is a process-oriented hierarchy like CCS, which is different from the subnet-oriented hierarchy in the Jensen's hierarchical colored Petri net. In a process-oriented hierarchy, a hierarchical unit is a process, which is more natural for cooperating and decentralized discrete event control systems. This paper also proposes a design methodology for MENDEL nets. Although many Petri net tools have been proposed, most tools support only drawing, simulation, and analysis of Petri nets; few tools support the design methodology for Petri nets. While Petri nets are good final design documents easy to understand, analyzable, and executable it is often difficult to write Petri nets directly in an earlier design phase when the system structure is obscure. A proposed design methodology makes a designer to construct MENDEL nets systematically using causality matrices and temporal logic. Furthemore, constructed MENDEL nets can be automatically compiled into a concurrent programming language and executed on a parallel computer.

Net-Oriented Analysis and Design (NOAD) is defined as three items: (1) Various nets are utilized as an effective modeling method. (2) Inter-relationships among verious nets are determined. (3) Verification or analysis methods for nets are provided and they are implemented based on the mathematical theory, that is Net theory. Very few methods have been presented to satisfy these three items. For example, the Real-Time SA method covers item (1) only. The Object-Oriented Analysis and Design method (OOA/OOD) covers items (1) and (2). NOAD can be regarded as an extension to OOA/OOD. This paper discusses how effectively various nets have been used in actual software development support metnods and tools and evaluates such several methods and tools from the NOAD viewpoint.

Stochastic Petri Nets and Generalized Stochastic Petri Nets as well as other extensions to Stochastic Petri Nets have been widely applied as a model of asynchronous concurrent process, or as an aid to analyze or design concurrent systems. This paper presents an Extended Stochastic Petri Net model for a shift processing system in which three kinds of sink may occur and an arbitrary time distribution is incorporated, provides an analytical method based on a Markov renewal process with some non-regeneration points to clarify the probabilistic behavior of the system, and finally evaluates the performance of the system with numerical values.

A job shop system typically seen in flexible manufacturing systems (FMS) is a system composed of a set of machines and a various kind of jobs processed with the machines. A production system of semiconductor fabrication is an example of job shop systems, which has main features of repetitive processes of one part and set-up times required for machines processing different types of parts. On the other hand, timed Petri nets are used for modelling and analyzing a wide variety of discrete event systems. There are many applications of timed Petri nets to the scheduling problems of job shop systems. The performance evaluation and steady state behaviors are studied by using the maximum cycle time of timed marked graphs. The aim of this paper is to propose a new model for production systems including repetitive processes and set-up time requirements which enables the quantitative analysis of real time system performance. In job shop systems such as a semiconductor fabrication system, it takes considerable amount of set-up time to prepare different types of chemical reactions and the model should take account of a set-up time for each machine. We focus upon the relationship between facility utilization factor and production cycle time in the steady state. In the proposed model, the minimum total set-up time can be attained. Quantitative relationship between utilization factor and production cycle time is derived by using the proposed model. A utilization factor of a system satisfying a given limit of the cycle time is evaluated, and the improvement of the utilization factor is considered. Conversely, we consider the improvement of the cycle time of a system satisfying a given limit of utilization factor.

This paper describes a modeling of the cryptography based on a concept of Petri nets. Movement of tokens in the net model shows a dynamic behavior of systems. On the other hand, the cryptography is considered as a bit operation, so that we can point out a common property between the net structure and the cryptography, which provides our idea that movement of tokens of the net model corresponds to a bitoperation of the cryptography. Some effective keys in the net model are considered by means of the net elements, which are based on T-invariant and net structures. It is shown that the keys of the net structured cryptography provide reasonable strength comparing with the data encryption standard (DES).

The subject of the paper is to propose two approximation algorithms FM_SPLA, FM_DPLA for priority-list scheduling in timed Petri nets. Their capability is compared with that of existing algorithms SPLA, DPLA through experimental results, where SPLA and DPLA have previously been proposed by the authors.

The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect M , X and PN (a sequence of transitions, with the first transition firable on M , such that every transition t can fire prescribed number X(t) of times). The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.

Recent trends in down-sizing have resulted in the development of client server systems for many industries. This paper considers the application of stochastic Petri nets with general firing times for modeling of a concatenated client server system and the use of discrete-event simulation methods for stochastic Petri nets to study its behavior. This approach enables us to assess the most appropriate resource set of a concatenated client server system on the quantitative basis of the performability and the occurrence of system down conditions. Thus, system consultation, a new application of stochastic Petri nets, is presented.

The subject of the paper is to analyze time complexity of the minimum modification problem in the Horn clause propositional logic. Given a set H of Horn clauses and a query Q in propositional logic, we say that Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens among clauses of H. Suppose that Q is not provable over H, and we are going to modify H and Q into H and Q , respectively, such that Q is provable over H . The problem of making such modification by minimum variable deletion (MVD), by minimum clause addition (MCA) or by their combination (MVDCA) is considered. Each problem is shown to be NP-complete, and some approximation algorithms with their experimental evaluation are given.

The subject of the paper is to analyze time complexity of the minimum axiom set problem (MASHC) in the Horn clause propositional logic. MASHC is defined by "Given a set H of Horn clauses and a query Q, all in propositional logic, such that Q is provable over H, find an axiom set of minimum cardinality, HH, with respect to Q, where Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens starting from clauses of H under the assumption that all of them are originally assumed to be true". If Q is provable over H then H is called an axiom set (with respect to Q). As stated in the definition of MASHC, detecting if Q is provable over H is required. This leads us to a problem, called the provability detecting problem (PDPHC), defined by "Given a set H of Horn clauses and a query Q in propositional logic, determine if Q is provable over H". First an O(σ) algorithm BFSHC for PDPHC is given based on the breadth-first search, where σ is the formula size of a given set of Horn clauses. For MASHC, it is shown that the problem is NP-complete, and an O(σ) approximation algorithm FMAS is given. Its experimental evaluation is also presented.